1. Field
The present invention pertains to the field of solving constraint satisfaction problems and, in particular, to solving such problems using weighted constraints and heterogeneous types of data.
2. Related Art
Constraint satisfaction problems (CSP) can be used in a wide variety of different fields including scheduling, resource allocation, planning, time tabling, routing, test generation and configuration. A classical CSP includes at least three components:
A set of parameters X={x1, . . . , xi} for a total of i parameters;
Domains D setting boundaries for the possible values for each of the parameters D={d1, . . . , di} for the set of i parameters; and                A set of constraints C={c1, c2, c3, c4}.        
The goal of the classical CSP is to find a complete solution which is an assignment of values to all of the parameters X which satisfy all of the constraints C. Most classical systems deal with either linear programming (LP) or integer programming (IP) in finite domains D.
The most general type of classical CSP creates a random solution set for all of the parameters and tests to determine whether the solution set satisfies all of the constraints. If there is a failure, new values are chosen for all of the parameters and the process is repeated. The process is continued, repeating the selection of new values and testing them, until a satisfactory solution is found.
CSP solvers have been improved by using the results at each test and making small changes or guided changes. There are a variety of different approaches to selecting the set of values to solve the CSP. These can include hill climbing, minimum conflicts, random lot, tabu search, simulated annealing, GLS (Guided Local Search), GENET (Generic Neural NETwork), GSAT (Greedy SATisfiablity), and many different back tracking processes. Each of these improvements tries to select values for parameters based on prior selections or prior satisfaction tests.
CSP solvers. despite these improvements, can still require extensive processing power to arrive at a solution. The amount of processing required increases with the complexity of the CSP. In addition CSP semantics greatly limit flexibility in describing a problem and, for problems with multiple solutions, in steering or orienting the result toward a particular range of parameter values.